package coinChange;

import java.util.Arrays;

public class Solution {
    public static int coinChange(int[] coins, int amount) {
        int dp[]=new int[amount+1];
        for (int i=0;i<=amount;i++) dp[i]=23333;
        dp[amount]=0;
        for (int i=amount;i>=0;i--)
          if (dp[i]==23333) continue;
          else
        	  for (int j=0;j<coins.length;j++){
        		  if ((i-coins[j]>=0) && (dp[i-coins[j]]>dp[i]+1))
                     dp[i-coins[j]]=dp[i]+1;
        	  }
        if (dp[0]==23333) return -1;
        else return dp[0];
    }
/*  322.coin change
 *  暖手DP题 
 *  1.判断贪心算法不可行
 *  2.时间复杂度判断（话说leetcode不给数据范围大丈夫？）
 *  3.状态转移dp[i]=min(dp[i],dp[i+coins[j]]+1)
 *  4.正推反推看心情
 * 
 */
}